package com.zh.note.leetcode.backtracking;

/**
 * 37. 解数独
 * <p>
 * 编写一个程序，通过填充空格来解决数独问题。
 * <p>
 * 数独的解法需 遵循如下规则：
 * <p>
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 */
public class LC_37_solveSudoku {

    public void solveSudoku(char[][] board) {
        dfs(board);

    }

    private boolean dfs(char[][] board) {
        for (int i = 0; i < board.length; i++) {     // 遍历行
            for (int j = 0; j < board[0].length; j++) {     // 遍历列
                // 如果是空格
                if (board[i][j] == '.') {
                    for (char k = '1'; k <= '9'; k++) {
                        if (isValid(i, j, k, board)) {  // (i, j) 这个位置放k是否合适
                            board[i][j] = k;  // 放置k
                            boolean res = dfs(board);
                            if (res == true) {
                                return true;
                            }
                            board[i][j] = '.'; // 回溯
                        }
                    }
                    return false;  // 9个数都试完了，都不行，那么就返回false
                }
            }
        }
        return true;

    }

    private boolean isValid(int row, int col, char val, char[][] board) {
        // 同行是否重复
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == val) {
                return false;
            }
        }
        // 同列是否重复
        for (int j = 0; j < 9; j++) {
            if (board[j][col] == val) {
                return false;
            }
        }
        // 9宫格里是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) {
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == val) {
                    return false;
                }
            }
        }
        return true;
    }
}
